Ông tên thật là Tạ Thái An, sinh ngày 25 tháng 10 năm 1921 tại xã Bảo Khê, huyện Kim Động (nay thuộc thành phố Hưng Yên), tỉnh Hưng Yên, con ông Tạ Quang Khai và bà Nguyễn Thị Tành. Cha ông là một tiểu chủ yêu nước làm nghề thợ may, do tham gia phong trào yêu nước nên bị Pháp lùng bắt, vì vậy đã đưa gia đình lên sinh sống tại vùng Tràng Định - Thất Khê (Lạng Sơn). Tuổi thơ ông lớn lên tại vùng rừng núi này.

Sau khi hoàn thành lớp nhất (tương đương với lớp 5 hiện nay), ông được cha gửi xuống Hà Nội ở nhờ ông Mai Phúc Tường (hiệu Quảng Thái) ở 29 Hàng Bồ để học tiếp bậc trung học tại trường tư thục Thăng Long[1]. Sau này khi ông Hoàng Minh Thảo hoạt động cách mạng đã được gia đình ông Mai Phúc Tường che giấu hoạt động. Cũng trong quãng thời gian này, trong những lần về Lạng Sơn nghỉ hè, ông giác ngộ cách mạng qua những đợt tham gia buổi tuyên truyền của Đảng. Năm 1937, Tạ Thái An được xếp vào danh sách cảm tình Đảng tại cơ sở Đảng ở Lạng Sơn và tham gia Đoàn thanh niên dân chủ của Đảng Cộng sản Việt Nam tổ chức, lấy bí danh hoạt động là Tạ Quang. Năm 1941, ông tham gia Việt Minh, rồi được cử đi học quân sự ở Liễu Châu, Trung Quốc. Cuối năm 1944, ông tham gia gây dựng cơ sở chính trị và xây dựng lực lượng du kích ở vùng biên giới Lạng Sơn.

Sau khi về nước, ngày 7 tháng 1 năm 1945, tham gia Ban phụ trách công tác biên giới của Tổng bộ Việt Minh, Ủy viên dự khuyết Tỉnh ủy lâm thời Lạng Sơn. Ngày 3 tháng 3 năm 1945, ông gia nhập Đảng Cộng sản Đông Dương và tham gia giành chính quyền ở Lạng Sơn. Cái tên Hoàng Minh Thảo ra đời trong thời gian này và gắn bó với ông cho đến tận cuối đời.